package demo1;
//定义一棵搜索树
public class BinarySearchTree {
    static class TreeNode {
        private int value;
        private TreeNode left;
        private TreeNode right;
        public TreeNode(int value) {
            this.value = value;
        }
    }
    private  TreeNode root = null;

    /**查找指定元素
     *时间复杂度：
     *      O(logN)     最坏情况下：O(N)
     * @param key
     * @return
     */
    public TreeNode search(int key) {
        if(root == null) {
            return null;
        }
        TreeNode cur = root;
        while (cur != null) {
            if(cur.value == key) {
                return cur;
            }else if(cur.value > key) {
                //说明key在左树
                cur = cur.left;
            }else {
                //说明key在右树
                cur = cur.right;
            }
        }
        return null;//当整棵树都没有找到key，返回null
    }

    /**插入元素
     * 时间复杂度：
     *
     * @param val
     * @return
     */
    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) {
            root = node;
            return true;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null) {
            if(cur.value == val) {
                return false;
            }else if(cur.value > val) {
                prev = cur;
                cur = cur.left;
            }else {
                prev = cur;
                cur = cur.right;
            }
        }
        if(prev.value > val) {
            prev.left = node;
        }else {
            prev.right = node;
        }
        return true;
    }

    public void remove(int val) {

    }
}
